package interview;

public class Interview_day4 {
	
	
	/**
	 * Given an array consists of negative and positive elements,
	 * put all negative ones on the left and positive elements on the right
	 * and keep their original order.
	 * Ex:
	 * [3,5,-1,6,-6,5]----->[-1,-6,3,5,6,5]
	 * 
	 * Analysis:
	 * Use insertion, every time we find a negative element, we do insertion
	 * @param a
	 */
	public static void specialSort(int[] a){
		if(a == null || a.length == 1) return;
		
		int ind = 0;
		for(int i = 0 ; i < a.length ; i++){
			if(a[i] < 0){//do insertion
				int temp = a[ind];
				a[ind] = a[i];
				for(int j = i ; j >= ind+2 ; j--)//must from right to left
					//because we change the right first.
					a[j] = a[j-1];//right equals to the left
				a[ind+1] = temp;
				ind++;
				i--;
			}
		}
		
		System.out.println();
		for(int i : a)
			System.out.print(i+", ");
		System.out.println();
		
	}

	/**
	 * Find the element with number of appearance larger than n/2
	 * @param a
	 */
	public static void majorityElement(int[] a){
		if(a == null) return;
		int maj_idx = 0, count = 1;
		for(int i = 1 ; i < a.length ; i++){
			if(a[i] == a[maj_idx]) count++;
			else count--;
			if(count == 0){
				maj_idx = i;
				count = 1;
			}
		}
		count = 0;
		for(int i = 0 ; i < a.length ; i++)
			if(a[i] == a[maj_idx]) count++;
		if(count > a.length/2) System.out.println("The majority element is: " + a[maj_idx]);
		else System.out.println("No majority element.");
	}
	
	
	public static void findHalf(int[] a){
		if(a == null) return;
		int maj_idx = 0, count = 1;
		for(int i = 1 ; i < a.length ; i++){
			if(a[i] == a[maj_idx]) count++;
			else count--;
			if(count == -1){
				maj_idx = i;
				count = 1;
			}
		}
		count = 0;
		for(int i = 0 ; i < a.length ; i++)
			if(a[i] == a[maj_idx]) count++;
		if(count == a.length/2) System.out.println("The half element is: " + a[maj_idx]);
		else System.out.println("No half element.");
	}
	
	
	public static void rotateMatrix(int[][] m){
		
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		specialSort(new int[]{3,5,-1,6,-6,5});
		 majorityElement(new int[]{2,3,4,2,3,4,4,3,3,3,2,2,5});
		 findHalf(new int[]{2,3,3,2,2,1});
	}

}
